Unidade 1: Fundamentos
2 -
Introdução a Algoritmos
2.1 - Noções de Lógica
·
A palavra lógica relaciona-se com a idéia de racionalidade e
coerência.
·
Algumas definições:
o " a
lógica é a arte de bem pensar"
o " a
lógica é a ciência das formas do pensamento"
o " a
lógica nos ensina a colocar ordem no pensamento"
·
Exemplo:
o Todo
mamífero e um animal.
o Todo
cavalo e um mamífero.
o Portanto,
todo cavalo e um animal.
·
A lógica no dia-a-dia
o Quando
queremos escrever, falar ou agir corretamente precisamos colocar ordem no
pensamento, isto é, utilizar lógica.
o Exemplo:
§
A gaveta está fechada.
§
A caneta está dentro da gaveta.
§
Então, precisamos abrir a gaveta para depois pegar a caneta.
·
A lógica de programação
o Em que
consiste?
A lógica de programação consiste no uso correto das leis do pensamento, da "ordem da razão" e de processos de raciocínio e simbolização formais na programação de computadores.
o Qual o
objetivo?
Permitir a
resolução de problemas específicos com soluções de boa qualidade.
o O raciocínio
lógico pode ser expresso através de várias linguagens:
§
no contexto humano - utiliza-se a palavra escrita/falada
que, por sua vez, se baseia num determinado idioma, mas, independente do
idioma, tem-se o mesmo raciocínio.
§
no contexto computacional - utilizam-se as linguagens de
programação
o Vamos
utilizar uma forma de representação mais genérica (livre de detalhes
computacionais) e que traduza mais fielmente o raciocínio da lógica de
programação: ALGORITMOS
o Então ...
O objetivo
da lógica de programação é a construção de algoritmos corretos e válidos.
2.2 - Sobre Algoritmos
·
Definição: um algoritmo consiste numa seqüência de passos
que visam atingir um objetivo bem definido.
·
Para especificar uma seqüência de passos , precisamos
utilizar ordem, ou seja "pensar com ordem", portanto, precisamos
utilizar lógica.
·
Algoritmos são comuns no nosso cotidiano. Exemplo: uma
receita de bolo - nela está escrita uma série de ingredientes necessários e uma
seqüência de diversos passos (modo de preparar) que devem ser fielmente
cumpridos para realizar a tarefa.
·
IMPORTANTE!!
Os algoritmos fixam um padrão de comportamento a ser
seguido; uma norma de execução a ser trilhada, visando alcançar, como resultado
final, a solução de um problema
·
Por que usar algoritmos?
1. abstração
- todo o esforço é concentrado na resolução do problema e não em detalhes
computacionais que podem ser acrescentados posteriormente
2. portabilidade
- uma solução algorítmica pode ser traduzida para qualquer linguagem de
programação
·
Vejamos um outro exemplo... Deseja-se escrever um algoritmo, usando português coloquial,
para resolver um problema bastante simples, qual seja: trocar uma lâmpada
queimada por uma lâmpada nova não queimada.
Algoritmo 1.1 - Trocar uma lâmpada queimada
·
pegar uma escada;
·
posicionar a escada debaixo da lâmpada;
·
buscar uma lâmpada nova;
·
subir na escada;
·
retirar a lâmpada queimada;
·
colocar lâmpada nova;
Reexaminando o algoritmo 2.1,
notamos que ele tem um objetivo bem definido: trocar uma lâmpada queimada. Porém
o algoritmo não atingirá seu objetivo se a lâmpada nova estiver queimada. Para
tal, acrescentamos um teste condicional (estrutura seletiva).
Algoritmo 1.2 - Trocar uma lâmpada queimada (uso de teste condicional)
·
pegar uma escada;
·
posicionar a escada debaixo da lâmpada;
·
buscar uma lâmpada nova;
·
subir na escada;
·
retirar a lâmpada queimada;
·
colocar lâmpada nova;
·
se a lâmpada nova não acender, então:
o retirar a
lâmpada queimada;
o colocar
lâmpada nova;
o se a
lâmpada nova não acender, então:
§
retirar a lâmpada queimada;
§
colocar a lâmpada nova;
§
se a lâmpada nova não acender, então:
o
retirar a lâmpada queimada;
o
colocar a lâmpada nova;
. .
.
até
quando????
O Algoritmo 1.2 não está terminado.
As ações cessarão quando conseguirmos colocar uma lâmpada que acenda (objetivo
do algoritmo). Ao invés de reescrevermos várias vezes um conjunto de ações,
podemos alterar o fluxo seqüencial de execução para permitir que ações sejam
re-executadas quantas vezes forem necessárias. Precisamos expressar essa repetição (estrutura de repetição) garantindo uma condição de parada.
Algoritmo 1.3 - Trocar uma lâmpada queimada (uso de estruturas de repetição)
·
pegar uma escada;
·
posicionar a escada debaixo da lâmpada;
·
buscar uma lâmpada nova;
·
subir na escada;
·
retirar a lâmpada queimada;
·
colocar lâmpada nova;
·
enquanto lâmpada nova não acender, faça
§
retirar a lâmpada queimada;
§
colocar lâmpada nova;
·
Um exemplo mais envolvendo processamento de dados (tipo de
problema que realmente nos interessa!): Deseja-se elaborar um algoritmo que
escreva os termos da série de Fibonacci inferiores a L.
A série de
Fibonacci: 1 1 2 3 5 8 13 ...
Algoritmo 2 - Calcular a série de Fibonacci
·
pegar o valor L;
·
atribuir o valor 1 ao primeiro termo;
·
se o primeiro termo for menor do que L, então
o escreva-o;
·
atribuir o valor 1 ao segundo termo;
·
se o segundo termo for menor do que L, então
o escreva-o;
·
calcular novo termo somando os dois anteriores;
·
enquanto novo termo for menor do que L, faça:
o escreva-o;
o atualiza
os termos anteriores;
o calcule
novo termo somando os dois anteriores;
·
Quando o nosso algoritmo estará completo?
o Um
algoritmo é considerado completo quando seus comandos (ações/instruções) forem
do entendimento do destinatário.
o Se um
comando não estiver claro, este deve ser desdobrado em novos comandos, que
constituirão um refinamento do comando inicial. Em alguns casos, devem ser
feitos refinamentos sucessivos do algoritmo.
o No
algoritmo 2, dependendo do tipo de destinatário, poderia ser necessário
detalhar algumas ações, como por exemplo, a ação atualiza os termos anteriores. Nesse caso, teríamos:
...
§
primeiro termo passa a ter o valor do segundo termo;
§
segundo termo passa a ter o valor do novo termo;
...
·
Como representar nossos algoritmos?
·
Vamos continuar a utilizar a nossa linguagem natural,
o português, para representar
algoritmos, procurando restringir o vocabulário e as estruturas sintáticas para
evitar ambigüidade e obter precisão e clareza.
·
É interessante ressaltar que, a idéia de restringir o uso do
português para facilitar a descrição dos algoritmos muito se aproxima da
maneira pela qual as linguagens de programação reais (como C e Pascal) representam
os algoritmos que serão executados pelo computador.
2.3 - Itens
Fundamentais dos Nossos Algoritmos
·
Tipos de Dados:
o Constantes:
§
São os dados que não sofrem modificação durante a execução
do algoritmo.
§
Exemplos: 123, 12.34, "Campina Grande", VERDADE.
o Variáveis:
§
São os dados que sofrem modificação durante a execução do
algoritmo. É um contêiner que pode armazenar um tipo determinado de dado e cuja
identificação e dada através de um nome.
§
A área de uma círculo é processada pela fórmula descrita
abaixo:
área = pi
* raio 2
área =
3,14 * raio * raio
área e raio representam variáveis, uma vez que seus valores dependem de
qual círculo estamos considerando; 3,14 é um valor constante utilizado para
calcular a área de qualquer círculo.
§
No ambiente computacional cada variável corresponde a uma
porção (parte ou pedaço) de memória (memoria principal), cujo conteúdo pode
variar durante a execução de um programa.
§
Embora uma variável possa assumir vários valores, ela só
pode armazenar um valor de cada vez.
§
Os identificadores das variáveis representam as
posições de memória (endereços de memória) que armazenam os dados. No exemplo anterior, área e raio são os
identificadores (nomes) das variáveis que armazenam respectivamente a área e o
raio do círculo.
o Expressões
aritméticas
São
expressões cujos resultados de suas avaliações são valores numéricos. As
expressões aritméticas são compostas de:
§
operadores: são os operadores aritméticos:
+, -, * e / - a precedência entre os
operadores é a mesma utilizada na álgebra comum, porém, parênteses podem mudar
a precedência.
§
operandos: constantes, variáveis e
expressões aritméticas.
o Expressões
lógicas
São
expressões utilizadas para representar condições cujos resultados de suas
avaliações são verdadeiro ou falso. As expressões lógicas são
compostas de:
§
operadores: são os operadores aritméticos:
=, ¹, <,
£, >,
³, não, e,
ou - a precedência entre os operadores, da maior para a menor, é mostrada a
seguir, porém, parênteses podem mudar a precedência.
o
não
o
=, ¹, <,
£, >,
³
o
e, ou
§
operandos: constantes, variáveis e
expressões.
o Comentários:
§
São informações adicionais acrescentadas ao algoritmo para
aumentar seu entendimento - não influencia na execução do algoritmo.
§
Utilizaremos como comentário uma frase iniciada por /* e terminada
por */.
§
Exemplo: área = 3,14 * raio * raio /* cálculo da área de um
círculo */
2.2 - Entrada
e Saída de Dados
·
permite-nos fornecer os dados que "alimentam" os
algoritmos e mostram os resultados processados pelos mesmos. Para os comandos de
entrada e saída, utilizaremos palavras como: leia, informe, escreva,
mostre, etc.
·
O comando leia, permite
atribuir o dado lido (externo ao algoritmo) à variável identificada.
·
Exemplo: leia raio - atribui o valor lido à variável raio
·
O comando escreva,
permite exibir o valor de constantes ou o conteúdo armazenado nas variáveis
identificadas.
·
Exemplo: escreva "o valor do raio é", raio -
escreve a constante "o valor do raio é" seguido do valor armazenado
na variável raio.
2.3 - Estruturas de Controle
·
As estruturas de controle determinam a seqüência de execução
(fluxo de execução) das ações dos algoritmos.
·
Existem três tipos de estruturas de controle: estrutura
seqüencial, estrutura de seleção, estrutura de repetição. Vejamos um pouco mais
sobre cada uma delas:
2.3.1 - Estrutura
Seqüencial:
·
por via de regra, as ações descritas num algoritmo serão
executadas numa seqüência linear, isto é, da primeira à última, na ordem em que
aparecem.
·
modelo geral de um algoritmo:
algoritmo
/* corpo
do algoritmo */
ação1;
ação2;
...
açãoN;
fim do
algoritmo
Algoritmo 4 - Cálculo da média aritmética de quatro valores
algoritmo
/* Obtenção da
notas */
escreva
"Informe as notas do aluno: "
leia nota1,
nota2, nota3, nota4
/* Cálculo da
média */
média = (nota1
+ nota2 + nota3 + nota4) / 4;
escreva
"Média calculada: " média
fim do algoritmo
2.3.2 - Estruturas
de Seleção
·
permite a escolha de um conjunto de ações a serem executadas
quando a condição for ou não satisfeita.
·
seleção simples - forma geral:
se <condição>
/* ações caso a condição
seja verdadeira */
. . .
·
seleção composta - forma geral:
se <condição>
/* ações caso a condição
seja verdadeira */
. . .
senão
/* ações caso a condição
seja falsa */
. . .
·
Exercício em sala: modifique o algoritmo 4 de modo que seja
avaliado se o aluno obteve nota maior do que 7.0; deve-se informar sobre a
aprovação ou não do aluno.
·
é possível agruparmos várias seleções numa única estrutura
denominada: seleção encadeada.
·
forma geral de uma seleção encadeada:
se
<condição1>
/* ações caso a condição1 seja verdadeira */
senão se
<condição2>
/* ações caso a condição2 seja verdadeira */
senão se
<condição3>
/* ações caso a condição3 seja verdadeira */
. . .
senão se
<condiçãoN>
/* ações caso a condiçãoN seja verdadeira */
senão
/* ações caso todas as condições sejam falsas */
·
Exercício em sala: escreva um algoritmo que determine se um
conjunto de 3 valores (fornecidos pelo usuário) - lado1, lado2, lado3 - formam
um triângulo e, se forem, verificar se compõem um triângulo equilátero,
isósceles ou escaleno. Informar se não compuserem um triângulo.
Algoritmo 5 - Verificar se três lados formam um triângulo e que tipo de
triângulo
algoritmo
/* Obtenção dos
dados */
leia(lado1,
lado2, lado3);
se (lado1 <
lado2+lado3) e (lado2 < lado1+lado3) e
(lado3
< lado2+lado1) /* Testa se é triângulo */
se
(lado1=lado2) e (lado2=lado3) /* Testa se é equilátero */
escreva "Os valores fornecidos formam um triângulo",
" equilátero."
senão se
(lado1 = lado2) ou (lado2 = lado3) ou (lado1 = lado3)
/* Testa se é isósceles */
escreva "Os valores fornecidos formam um triângulo",
" isósceles"
senão /* É
escaleno */
escreva
"Os valores fornecidos formam um triângulo",
" escaleno"
fim do algoritmo
·
Seleções encadeadas podem seguir um mesmo padrão lógico:
1 - Padrão
se-então-se:
·
Suponha um comando qualquer que deva ser executado apenas
quando as condições, condição1 e condição2, forem verdadeiras. Então teremos a
seguinte situação:
se
<condição1>
se <condição2>
comando(s)
·
Nesse caso é melhor utilizar:
se
<condição1> e <condição2>
comando(s)
2 - Padrão
se-senão-se
·
Suponha que uma variável var só possa assumir os valores valor1 e valor2; e que
existam comandos diferentes para cada valor armazenado em var. Então teremos a seguinte situação:
se var =
valor1
comando1
se var =
valor2
comando2
·
Melhorando o desempenho dessa estrutura (diminuindo a
quantidade média de testes):
se var =
valor1
comando1
senão se
var = valor2
comando2
2.3.3 - Estruturas
de repetição
·
Quando um trecho de programa deve ser repetido ao longo do
algoritmo, ao invés de reescrevê-lo várias vezes utilizam-se laços de
repetição.
·
O número de execuções de um laço de repetição pode ser
indeterminado, mas sempre será finito.
·
Tipos de laços:
o Laço com número de repetições indeterminado
A condição
de parada da repetição só ocorrerá conhecida num futuro imprevisível para o
algoritmo – o número de repetições não pode ser previsto.
enquanto
<condição> faça
comando(s) a repetir
o Exemplo:
calcular a média aritmética de quatro notas para um conjunto de alunos.
Algoritmo 6 - Calcular a média aritmética de 4 notas para vários alunos,
perguntando para cada aluno se existe outra média a calcular
algoritmo
resposta<span style="mso-char-type: symbol;
mso-symbol-font-family: Symbol; font-size: 16.0pt; mso-bidi-font-size: 10.0pt;
font-family: Symbol; mso-ascii-font-family: Arial; mso-fareast-font-family:
Times New Roman; mso-hansi-font-family: Arial; mso-bidi-font-family: Arial;
mso-ansi-language: PT-BR; mso-fareast-language: PT-BR; mso-bidi-language: AR-SA">
= </span>"S";
enquanto
(resposta = "S") faça
/* Obtenção das notas */
escreva "Informe as notas do aluno: "
leia nota1, nota2, nota3, nota4
/* Cálculo da média */
média = (nota1 + nota2 + nota3 + nota4) / 4
escreva "Média calculada: ", média
escreva "Deseja calcular outras média de aluno (S/N)?"
leia resposta
fim do algoritmo
o Exemplo:
modificar o algoritmo 6, parando quando encontrar uma nota menor que zero.
Algoritmo 7 - Calcular a média aritmética de 4 notas para vários alunos
e parar quando aparecer uma nota negativa
algoritmo
/*
Obtenção das notas para o primeiro aluno */
escreva
"Informe as notas do aluno: "
leia
nota1, nota2, nota3, nota4
enquanto
(nota1 >= 0 e nota2 >= 0 e nota3
>= 0 e nota4 >= 0) faça
/* Cálculo da média */
média = (nota1 + nota2 + nota3 + nota4) / 4
escreva "Média calculada: ", média
/* Obtenção das notas para os demais alunos */
escreva "Informe as notas do aluno: "
leia nota1, nota2, nota3, nota4
fim do algoritmo
o Laço com número de repetição determinado
A condição
de parada da repetição pode ocorrerá num futuro previsível para o algoritmo – o
número de repetições pode ser previamente calculado.
contador =
valorInicial
enquanto
contador <= valorLimite faça
comando(s) a repetir
contador = contador + valorDoIncremento
o Exemplo:
modificar o algoritmo 6, considerando a quantidade de alunos igual a 50.
Algoritmo 8 - Calcular a média aritmética de 4 notas para 50 alunos
algoritmo
numAlunos
= 1
enquanto
numAlunos < = 50 faça
/* Obtenção da notas */
escreva "Informe as notas do aluno: "
leia nota1, nota2, nota3, nota4
/* Cálculo da média */
média = (nota1 + nota2 + nota3 + nota4) / 4
escreva "Média calculada: ", média
numAlunos = numAlunos + 1
fim do algoritmo
o Exemplo:
modificar o algoritmo 6, considerando uma determinada quantidade de alunos.
Algoritmo 9 - Calcular a média aritmética de 4 notas para um número
determinado de alunos
algoritmo
leia
totalDeAlunos
numAlunos
= 1
enquanto
numAlunos < = totalDEAlunos faça
/* Obtenção da notas */
escreva "Informe as notas do aluno: "
leia nota1, nota2, nota3, nota4
/* Cálculo da média */
média = (nota1 + nota2 + nota3 + nota4) / 4
escreva "Média calculada: ", média
numAlunos = numAlunos + 1
fim do algoritmo
Versão ".doc" do material apresentado acima (aqui)